{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e0fe4edd",
   "metadata": {},
   "source": [
    "# 习题\n",
    "## 习题1\n",
    "![image.png](./images/exercise1_1.png)\n",
    "### 解答思路\n",
    "- 列出C4.5的生成算法；\n",
    "- 使用sklearn的DecisionTreeClassifier类构建决策树，并使用graphviz包展示，默认是Gini，这里可以作为自编程的验证\n",
    "- 通过自编程实现C4.5算法生成决策树，并进行特征选择\n",
    "### 解答步骤\n",
    "#### 第1步：列出C4.5的生成算法\n",
    "![image-2.png](./images/exercise1_2.png)\n",
    "#### 第2步：调用sklearn的DecisionTreeClassifier类构建决策树\n",
    "DecisionTreeClassifier 是 scikit-learn（sklearn）库中的一个类，用于构建基于决策树的分类模型。决策树是一种基本的分类和回归方法，通过构建树状结构来对数据进行分类。\n",
    "\n",
    "DecisionTreeClassifier 的主要特点包括：\n",
    "\n",
    "1. 基于树状结构的分类器：通过构建一棵树来实现分类任务，每个节点代表一个特征，每个分支代表一个特征的取值，叶子节点代表一个类别。\n",
    "\n",
    "2. 特征选择：决策树分类器能够根据不同的特征选择策略（如信息增益、基尼系数等）自动选择最佳的特征进行分裂，从而实现对数据的分类。\n",
    "\n",
    "3. 易于解释：决策树模型生成的分类规则可以直观地呈现在树形结构中，便于解释和理解。\n",
    "\n",
    "4. 对异常值和缺失值具有较好的鲁棒性：决策树模型对异常值和缺失值的处理能力较强。\n",
    "\n",
    "DecisionTreeClassifier 类的常用方法和属性包括：\n",
    "\n",
    "- fit(X, y)：用训练数据 X 和标签 y 训练模型。\n",
    "- predict(X)：对测试数据 X 进行分类预测。\n",
    "- predict_proba(X)：返回每个样本属于各个类别的概率。\n",
    "- feature_importances_：返回特征重要性，即每个特征对分类结果的影响程度。\n",
    "在使用 DecisionTreeClassifier 时，可以通过设置不同的参数来调整模型的性能，例如树的最大深度、最小样本分裂数、叶子节点最小样本数等。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7cbce2fb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 10.0.1 (20240210.2158)\n",
       " -->\n",
       "<!-- Title: Tree Pages: 1 -->\n",
       "<svg width=\"270pt\" height=\"340pt\"\n",
       " viewBox=\"0.00 0.00 270.00 340.25\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 336.25)\">\n",
       "<title>Tree</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-336.25 266,-336.25 266,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<path fill=\"#bddef6\" stroke=\"black\" d=\"M214.62,-332.25C214.62,-332.25 103.38,-332.25 103.38,-332.25 97.38,-332.25 91.38,-326.25 91.38,-320.25 91.38,-320.25 91.38,-250.75 91.38,-250.75 91.38,-244.75 97.38,-238.75 103.38,-238.75 103.38,-238.75 214.62,-238.75 214.62,-238.75 220.62,-238.75 226.62,-244.75 226.62,-250.75 226.62,-250.75 226.62,-320.25 226.62,-320.25 226.62,-326.25 220.62,-332.25 214.62,-332.25\"/>\n",
       "<text text-anchor=\"start\" x=\"99.38\" y=\"-314.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">有自己的房子 ≤ 3.0</text>\n",
       "<text text-anchor=\"start\" x=\"127.5\" y=\"-299.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.48</text>\n",
       "<text text-anchor=\"start\" x=\"118.12\" y=\"-284.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 15</text>\n",
       "<text text-anchor=\"start\" x=\"120\" y=\"-269.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [6, 9]</text>\n",
       "<text text-anchor=\"start\" x=\"128.62\" y=\"-249.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 是</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<path fill=\"#f2c09c\" stroke=\"black\" d=\"M138,-202.75C138,-202.75 68,-202.75 68,-202.75 62,-202.75 56,-196.75 56,-190.75 56,-190.75 56,-121.25 56,-121.25 56,-115.25 62,-109.25 68,-109.25 68,-109.25 138,-109.25 138,-109.25 144,-109.25 150,-115.25 150,-121.25 150,-121.25 150,-190.75 150,-190.75 150,-196.75 144,-202.75 138,-202.75\"/>\n",
       "<text text-anchor=\"start\" x=\"64.75\" y=\"-185.45\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">有工作 ≤ 3.0</text>\n",
       "<text text-anchor=\"start\" x=\"67.75\" y=\"-170.45\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.444</text>\n",
       "<text text-anchor=\"start\" x=\"65.88\" y=\"-155.45\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 9</text>\n",
       "<text text-anchor=\"start\" x=\"64\" y=\"-140.45\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [6, 3]</text>\n",
       "<text text-anchor=\"start\" x=\"72.62\" y=\"-120.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 否</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M138.78,-238.47C135.21,-230.34 131.46,-221.8 127.79,-213.43\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"131.02,-212.1 123.8,-204.35 124.61,-214.91 131.02,-212.1\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.11\" y=\"-220.46\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">True</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<path fill=\"#399de5\" stroke=\"black\" d=\"M250,-192.62C250,-192.62 180,-192.62 180,-192.62 174,-192.62 168,-186.62 168,-180.62 168,-180.62 168,-131.38 168,-131.38 168,-125.38 174,-119.38 180,-119.38 180,-119.38 250,-119.38 250,-119.38 256,-119.38 262,-125.38 262,-131.38 262,-131.38 262,-180.62 262,-180.62 262,-186.62 256,-192.62 250,-192.62\"/>\n",
       "<text text-anchor=\"start\" x=\"187.25\" y=\"-175.32\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"start\" x=\"177.88\" y=\"-160.32\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 6</text>\n",
       "<text text-anchor=\"start\" x=\"176\" y=\"-145.32\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 6]</text>\n",
       "<text text-anchor=\"start\" x=\"184.62\" y=\"-125.08\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 是</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>0&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M179.22,-238.47C184.25,-227 189.66,-214.7 194.7,-203.22\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"197.78,-204.91 198.6,-194.35 191.37,-202.1 197.78,-204.91\"/>\n",
       "<text text-anchor=\"middle\" x=\"208.28\" y=\"-210.46\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">False</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<path fill=\"#e58139\" stroke=\"black\" d=\"M82,-73.25C82,-73.25 12,-73.25 12,-73.25 6,-73.25 0,-67.25 0,-61.25 0,-61.25 0,-12 0,-12 0,-6 6,0 12,0 12,0 82,0 82,0 88,0 94,-6 94,-12 94,-12 94,-61.25 94,-61.25 94,-67.25 88,-73.25 82,-73.25\"/>\n",
       "<text text-anchor=\"start\" x=\"19.25\" y=\"-55.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"start\" x=\"9.88\" y=\"-40.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 6</text>\n",
       "<text text-anchor=\"start\" x=\"8\" y=\"-25.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [6, 0]</text>\n",
       "<text text-anchor=\"start\" x=\"16.62\" y=\"-5.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 否</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M81.03,-108.95C77.06,-100.64 72.93,-91.97 68.97,-83.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.18,-82.27 64.71,-74.75 65.86,-85.28 72.18,-82.27\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<path fill=\"#399de5\" stroke=\"black\" d=\"M194,-73.25C194,-73.25 124,-73.25 124,-73.25 118,-73.25 112,-67.25 112,-61.25 112,-61.25 112,-12 112,-12 112,-6 118,0 124,0 124,0 194,0 194,0 200,0 206,-6 206,-12 206,-12 206,-61.25 206,-61.25 206,-67.25 200,-73.25 194,-73.25\"/>\n",
       "<text text-anchor=\"start\" x=\"131.25\" y=\"-55.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"start\" x=\"121.88\" y=\"-40.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 3</text>\n",
       "<text text-anchor=\"start\" x=\"120\" y=\"-25.95\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 3]</text>\n",
       "<text text-anchor=\"start\" x=\"128.62\" y=\"-5.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = 是</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M124.97,-108.95C128.94,-100.64 133.07,-91.97 137.03,-83.67\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"140.14,-85.28 141.29,-74.75 133.82,-82.27 140.14,-85.28\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.sources.Source at 0x17f25f710>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn import preprocessing\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from sklearn import tree\n",
    "import graphviz\n",
    "\n",
    "features = [\"年龄\", \"有工作\", \"有自己的房子\", \"信贷情况\"]\n",
    "X_train = pd.DataFrame([\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"是\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"好\"],\n",
    "    [\"中年\", \"是\", \"是\", \"好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"否\", \"一般\"]\n",
    "])\n",
    "y_train = pd.DataFrame([\"否\", \"否\", \"是\", \"是\", \"否\",\n",
    "                        \"否\", \"否\", \"是\", \"是\", \"是\",\n",
    "                        \"是\", \"是\", \"是\", \"是\", \"否\"])\n",
    "class_names = [str(k) for k in np.unique(y_train)]\n",
    "# 数据预处理\n",
    "# 将标签（label）进行编码，将类别型的标签转换为数值型的编码。\n",
    "le_x = preprocessing.LabelEncoder()\n",
    "le_x.fit(np.unique(X_train))\n",
    "# 使用 LabelEncoder 对象将训练数据中的所有特征进行编码转换。\n",
    "X_train = X_train.apply(le_x.transform)\n",
    "# 调用sklearn的DecisionTreeClassifier建立决策树模型\n",
    "model_tree = DecisionTreeClassifier()\n",
    "# 训练模型\n",
    "model_tree.fit(X_train, y_train)\n",
    "\n",
    "# 导出决策树的可视化文件，文件格式是dot\n",
    "dot_data = tree.export_graphviz(model_tree, out_file=None,\n",
    "                                feature_names=features,\n",
    "                                class_names=class_names,\n",
    "                                filled=True, rounded=True,\n",
    "                                special_characters=True)\n",
    "# 使用graphviz包，对决策树进行展示\n",
    "graph = graphviz.Source(dot_data)\n",
    "# 可使用view方法展示决策树\n",
    "# 中文乱码：需要对源码_export.py文件（文件路径：sklearn/tree/_export.py）修改，\n",
    "# 在文件第451行中将helvetica改成SimSun\n",
    "graph\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5c05c974",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|--- 有自己的房子 <= 3.00\n",
      "|   |--- 有工作 <= 3.00\n",
      "|   |   |--- class: 否\n",
      "|   |--- 有工作 >  3.00\n",
      "|   |   |--- class: 是\n",
      "|--- 有自己的房子 >  3.00\n",
      "|   |--- class: 是\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 打印决策树\n",
    "tree_text = tree.export_text(model_tree, feature_names=features)\n",
    "print(tree_text)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "284dbf1f",
   "metadata": {},
   "source": [
    "#### 第3步：自编程实现C4.5算法生成决策树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b34d4dc7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{\n",
       "   \"node_type\": \"internal\",\n",
       "   \"feature_name\": \"有自己的房子\",\n",
       "   \"class_name\": null,\n",
       "   \"child_nodes\": [\n",
       "      {\n",
       "         \"condition\": \"否\",\n",
       "         \"sub_tree\": {\n",
       "            \"node_type\": \"internal\",\n",
       "            \"feature_name\": \"年龄\",\n",
       "            \"class_name\": null,\n",
       "            \"child_nodes\": [\n",
       "               {\n",
       "                  \"condition\": \"否\",\n",
       "                  \"sub_tree\": {\n",
       "                     \"node_type\": \"leaf\",\n",
       "                     \"feature_name\": null,\n",
       "                     \"class_name\": \"否\",\n",
       "                     \"child_nodes\": [],\n",
       "                     \"info_gain_ratio_value\": 0.0\n",
       "                  }\n",
       "               },\n",
       "               {\n",
       "                  \"condition\": \"是\",\n",
       "                  \"sub_tree\": {\n",
       "                     \"node_type\": \"leaf\",\n",
       "                     \"feature_name\": null,\n",
       "                     \"class_name\": \"是\",\n",
       "                     \"child_nodes\": [],\n",
       "                     \"info_gain_ratio_value\": 0.0\n",
       "                  }\n",
       "               }\n",
       "            ],\n",
       "            \"info_gain_ratio_value\": 1.0\n",
       "         }\n",
       "      },\n",
       "      {\n",
       "         \"condition\": \"是\",\n",
       "         \"sub_tree\": {\n",
       "            \"node_type\": \"leaf\",\n",
       "            \"feature_name\": null,\n",
       "            \"class_name\": \"是\",\n",
       "            \"child_nodes\": [],\n",
       "            \"info_gain_ratio_value\": 0.0\n",
       "         }\n",
       "      }\n",
       "   ],\n",
       "   \"info_gain_ratio_value\": 0.4325380677663126\n",
       "}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import json\n",
    "from collections import Counter\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "# 节点类\n",
    "class Node:\n",
    "    def __init__(self, node_type, class_name, feature_name=None,\n",
    "                 info_gain_ratio_value=0.0):\n",
    "        # 结点类型（internal或leaf）\n",
    "        self.node_type = node_type\n",
    "        # 特征名\n",
    "        self.feature_name = feature_name\n",
    "        # 类别名\n",
    "        self.class_name = class_name\n",
    "        # 子结点树\n",
    "        self.child_nodes = []\n",
    "        # Gini指数值\n",
    "        self.info_gain_ratio_value = info_gain_ratio_value\n",
    "\n",
    "    def __repr__(self):\n",
    "        return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False)\n",
    "\n",
    "    def add_sub_tree(self, key, sub_tree):\n",
    "        self.child_nodes.append({\"condition\": key, \"sub_tree\": sub_tree})\n",
    "        \n",
    "class MyDecisionTree:\n",
    "    def __init__(self, epsilon):\n",
    "        # 阈值\n",
    "        self.epsilon = epsilon\n",
    "        self.tree = None\n",
    "\n",
    "    def fit(self, train_set, y, feature_names):\n",
    "        features_indices = list(range(len(feature_names)))\n",
    "        self.tree = self._fit(train_set, y, features_indices, feature_names)\n",
    "        return self\n",
    "\n",
    "    # C4.5算法\n",
    "    def _fit(self, train_data, y, features_indices, feature_labels):\n",
    "        LEAF = 'leaf'\n",
    "        INTERNAL = 'internal'\n",
    "        class_num = len(np.unique(y))\n",
    "\n",
    "        # （1）如果训练数据集所有实例都属于同一类Ck\n",
    "        label_set = set(y)\n",
    "        if len(label_set) == 1:\n",
    "            # 将Ck作为该结点的类\n",
    "            return Node(node_type=LEAF, class_name=label_set.pop())\n",
    "\n",
    "        # （2）如果特征集为空\n",
    "        # 计算每一个类出现的个数\n",
    "        # most_common(): List the n most common elements and their counts from the most common to the least.  If n is None, then list all element counts.\n",
    "        class_len = Counter(y).most_common()\n",
    "        (max_class, max_len) = class_len[0]\n",
    "\n",
    "        if len(features_indices) == 0:\n",
    "            # 将实例数最大的类Ck作为该结点的类\n",
    "            return Node(LEAF, class_name=max_class)\n",
    "\n",
    "        # （3）按式(5.10)计算信息增益，并选择信息增益最大的特征\n",
    "        max_feature = 0\n",
    "        max_gda = 0\n",
    "        D = y.copy()\n",
    "        # 计算特征集A中各特征\n",
    "        for feature in features_indices:\n",
    "            # 选择训练集中的第feature列（即第feature个特征）\n",
    "            A = np.array(train_data[:, feature].flat)\n",
    "            # 计算信息增益\n",
    "            gda = self._calc_ent_grap(A, D)\n",
    "            if self._calc_ent(D) != 0:\n",
    "                # 计算信息增益比\n",
    "                gda /= self._calc_ent(D)\n",
    "            # 选择信息增益最大的特征Ag\n",
    "            if gda > max_gda:\n",
    "                max_gda, max_feature = gda, feature\n",
    "\n",
    "        # （4）如果Ag信息增益小于阈值\n",
    "        if max_gda < self.epsilon:\n",
    "            # 将训练集中实例数最大的类Ck作为该结点的类\n",
    "            return Node(LEAF, class_name=max_class)\n",
    "\n",
    "        max_feature_label = feature_labels[max_feature]\n",
    "\n",
    "        # （6）移除已选特征Ag\n",
    "        # np.setdiff1d() 函数是 NumPy 中用于计算两个数组的差集的函数。具体来说，它返回两个数组中不同元素的集合，即返回第一个数组中存在但第二个数组中不存在的元素。\n",
    "        sub_feature_indecs = np.setdiff1d(features_indices, max_feature)\n",
    "        sub_feature_labels = np.setdiff1d(feature_labels, max_feature_label)\n",
    "\n",
    "        # （5）构建非空子集\n",
    "        # 构建结点\n",
    "        feature_name = feature_labels[max_feature]\n",
    "        tree = Node(INTERNAL, class_name=None, feature_name=feature_name,\n",
    "                    info_gain_ratio_value=max_gda)\n",
    "\n",
    "        max_feature_col = np.array(train_data[:, max_feature].flat)\n",
    "        # 将类按照对应的实例数递减顺序排列\n",
    "        feature_value_list = [x[0] for x in Counter(max_feature_col).most_common()]\n",
    "        # 遍历Ag的每一个可能值ai\n",
    "        for feature_value in feature_value_list:\n",
    "            index = []\n",
    "            for i in range(len(y)):\n",
    "                if train_data[i][max_feature] == feature_value:\n",
    "                    index.append(i)\n",
    "\n",
    "            # 递归调用步（1）~步（5），得到子树\n",
    "            sub_train_set = train_data[index]\n",
    "            sub_train_label = y[index]\n",
    "            sub_tree = self._fit(sub_train_set, sub_train_label, sub_feature_indecs, sub_feature_labels)\n",
    "            # 在结点中，添加其子结点构成的树\n",
    "            tree.add_sub_tree(feature_value, sub_tree)\n",
    "\n",
    "        return tree\n",
    "\n",
    "    # 计算数据集x的经验熵H(x)\n",
    "    def _calc_ent(self, x):\n",
    "        # x取值集合\n",
    "        x_value_list = set([x[i] for i in range(x.shape[0])])\n",
    "        ent = 0.0\n",
    "        for x_value in x_value_list:\n",
    "            # 计算x出现的概率\n",
    "            p = float(x[x == x_value].shape[0]) / x.shape[0]\n",
    "            logp = np.log2(p)\n",
    "            ent -= p * logp\n",
    "\n",
    "        return ent\n",
    "\n",
    "    # 计算条件熵H(y/x)\n",
    "    def _calc_condition_ent(self, x, y):\n",
    "        x_value_list = set([x[i] for i in range(x.shape[0])])\n",
    "        ent = 0.0\n",
    "        for x_value in x_value_list:\n",
    "            sub_y = y[x == x_value]\n",
    "            temp_ent = self._calc_ent(sub_y)\n",
    "            ent += (float(sub_y.shape[0]) / y.shape[0]) * temp_ent\n",
    "\n",
    "        return ent\n",
    "\n",
    "    # 计算信息增益\n",
    "    def _calc_ent_grap(self, x, y):\n",
    "        base_ent = self._calc_ent(y)\n",
    "        condition_ent = self._calc_condition_ent(x, y)\n",
    "        ent_grap = base_ent - condition_ent\n",
    "\n",
    "        return ent_grap\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.tree)\n",
    "\n",
    "# 表5.1的训练数据集\n",
    "feature_names = np.array([\"年龄\", \"有工作\", \"有自己的房子\", \"信贷情况\"])\n",
    "X_train = np.array([\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"否\", \"好\"],\n",
    "    [\"青年\", \"是\", \"是\", \"一般\"],\n",
    "    [\"青年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"一般\"],\n",
    "    [\"中年\", \"否\", \"否\", \"好\"],\n",
    "    [\"中年\", \"是\", \"是\", \"好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"中年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"是\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"好\"],\n",
    "    [\"老年\", \"是\", \"否\", \"非常好\"],\n",
    "    [\"老年\", \"否\", \"否\", \"一般\"]\n",
    "])\n",
    "y = np.array([\"否\", \"否\", \"是\", \"是\", \"否\",\n",
    "              \"否\", \"否\", \"是\", \"是\", \"是\",\n",
    "              \"是\", \"是\", \"是\", \"是\", \"否\"])\n",
    "\n",
    "dt_tree = MyDecisionTree(epsilon=0.1)\n",
    "dt_tree.fit(X_train, y, feature_names)\n",
    "dt_tree\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "c56c6329",
   "metadata": {},
   "source": [
    "## 习题2\n",
    "![exercise2_1.png](./images/exercise2_1.png)\n",
    "### 解答思路：\n",
    "- 根据书中第5.5.1节平方误差最小的准则，列出最小二乘回归树生成算法（算法5.5）；\n",
    "- 编写代码，实现算法，并用表5.2训练数据进行验证。\n",
    "### 解题步骤：\n",
    "#### 第1步：算法5.5的最小二乘回归树生成算法\n",
    "根据书中第5.5.1节的算法5.5：\n",
    "![exercise2_2.png](./images/exercise2_2.png)\n",
    "#### 第2步：编写代码，实现算法，并用表5.2训练数据进行验证"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "42c978a4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{\n",
       "   \"value\": 5,\n",
       "   \"feature\": 0,\n",
       "   \"left\": {\n",
       "      \"value\": 3,\n",
       "      \"feature\": 0,\n",
       "      \"left\": 4.72,\n",
       "      \"right\": 5.57\n",
       "   },\n",
       "   \"right\": {\n",
       "      \"value\": 7,\n",
       "      \"feature\": 0,\n",
       "      \"left\": {\n",
       "         \"value\": 6,\n",
       "         \"feature\": 0,\n",
       "         \"left\": 7.05,\n",
       "         \"right\": 7.9\n",
       "      },\n",
       "      \"right\": {\n",
       "         \"value\": 8,\n",
       "         \"feature\": 0,\n",
       "         \"left\": 8.23,\n",
       "         \"right\": 8.85\n",
       "      }\n",
       "   }\n",
       "}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import json\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "# 节点类\n",
    "class Node:\n",
    "    def __init__(self, value, feature, left=None, right=None):\n",
    "        self.value = value.tolist()\n",
    "        self.feature = feature.tolist()\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def __repr__(self):\n",
    "        return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False)\n",
    "class MyLeastSquareRegTree:\n",
    "    def __init__(self, train_X, y, epsilon):\n",
    "        # 训练集特征值\n",
    "        self.x = train_X\n",
    "        # 类别\n",
    "        self.y = y\n",
    "        # 特征总数\n",
    "        self.feature_count = train_X.shape[1]\n",
    "        # 损失阈值\n",
    "        self.epsilon = epsilon\n",
    "        # 回归树\n",
    "        self.tree = None\n",
    "\n",
    "    def _fit(self, x, y, feature_count):\n",
    "        # （1）选择最优切分点变量j与切分点s，得到选定的对(j,s)，并解得c1，c2\n",
    "        (j, s, minval, c1, c2) = self._divide(x, y, feature_count)\n",
    "        # 初始化树\n",
    "        tree = Node(feature=j, value=x[s, j], left=None, right=None)\n",
    "        # 用选定的对(j,s)划分区域，并确定响应的输出值\n",
    "        if minval < self.epsilon or len(y[np.where(x[:, j] <= x[s, j])]) <= 1:\n",
    "            tree.left = c1\n",
    "        else:\n",
    "            # 对左子区域调用步骤（1）、（2）\n",
    "            tree.left = self._fit(x[np.where(x[:, j] <= x[s, j])],\n",
    "                                  y[np.where(x[:, j] <= x[s, j])],\n",
    "                                  self.feature_count)\n",
    "        if minval < self.epsilon or len(y[np.where(x[:, j] > s)]) <= 1:\n",
    "            tree.right = c2\n",
    "        else:\n",
    "            # 对右子区域调用步骤（1）、（2）\n",
    "            tree.right = self._fit(x[np.where(x[:, j] > x[s, j])],\n",
    "                                   y[np.where(x[:, j] > x[s, j])],\n",
    "                                   self.feature_count)\n",
    "        return tree\n",
    "\n",
    "    def fit(self):\n",
    "        self.tree = self._fit(self.x, self.y, self.feature_count)\n",
    "        return self\n",
    "\n",
    "    @staticmethod\n",
    "    def _divide(x, y, feature_count):\n",
    "        # 初始化损失误差\n",
    "        cost = np.zeros((feature_count, len(x)))\n",
    "        # 公式5.21\n",
    "        for i in range(feature_count):\n",
    "            for k in range(len(x)):\n",
    "                # k行i列的特征值\n",
    "                value = x[k, i]\n",
    "                y1 = y[np.where(x[:, i] <= value)]\n",
    "                c1 = np.mean(y1)\n",
    "                y2 = y[np.where(x[:, i] > value)]\n",
    "                if len(y2) == 0:\n",
    "                    c2 = 0\n",
    "                else:\n",
    "                    c2 = np.mean(y2)\n",
    "                y1[:] = y1[:] - c1\n",
    "                y2[:] = y2[:] - c2\n",
    "                cost[i, k] = np.sum(y1 * y1) + np.sum(y2 * y2)\n",
    "        # 选取最优损失误差点\n",
    "        cost_index = np.where(cost == np.min(cost))\n",
    "        # 所选取的特征\n",
    "        j = cost_index[0][0]\n",
    "        # 选取特征的切分点\n",
    "        s = cost_index[1][0]\n",
    "        # 求两个区域的均值c1,c2\n",
    "        c1 = np.mean(y[np.where(x[:, j] <= x[s, j])])\n",
    "        c2 = np.mean(y[np.where(x[:, j] > x[s, j])])\n",
    "        return j, s, cost[cost_index], c1, c2\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.tree)\n",
    "train_X = np.array([[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]).T\n",
    "y = np.array([4.50, 4.75, 4.91, 5.34, 5.80, 7.05, 7.90, 8.23, 8.70, 9.00])\n",
    "\n",
    "model_tree = MyLeastSquareRegTree(train_X, y, epsilon=0.2)\n",
    "model_tree.fit()\n",
    "model_tree\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "a873cad2",
   "metadata": {},
   "source": [
    "![image.png](./images/exercise2_3.png)\n",
    "## 习题3\n",
    "![image-2.png](./images/exercise3.png)\n",
    "<a href=\"https://datawhalechina.github.io/statistical-learning-method-solutions-manual/#/chapter05/ch05?id=%e4%b9%a0%e9%a2%9853\">详细证明</a>\n",
    "## 习题4\n",
    "![image-2.png](./images/exercise4.png)\n",
    "<a href=\"https://datawhalechina.github.io/statistical-learning-method-solutions-manual/#/chapter05/ch05?id=%e4%b9%a0%e9%a2%9854\">详细证明</a>\n",
    "# scikit-learn实例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "32f38f3b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuracy score used DecisionTreeClassifier to predict is 93.33%\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 10.0.1 (20240210.2158)\n",
       " -->\n",
       "<!-- Title: Tree Pages: 1 -->\n",
       "<svg width=\"565pt\" height=\"477pt\"\n",
       " viewBox=\"0.00 0.00 565.00 477.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 473)\">\n",
       "<title>Tree</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-473 561,-473 561,4 -4,4\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>0</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"388.5,-469 279.5,-469 279.5,-401 388.5,-401 388.5,-469\"/>\n",
       "<text text-anchor=\"middle\" x=\"334\" y=\"-451.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">x[0] &lt;= 5.45</text>\n",
       "<text text-anchor=\"middle\" x=\"334\" y=\"-436.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.5</text>\n",
       "<text text-anchor=\"middle\" x=\"334\" y=\"-421.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 70</text>\n",
       "<text text-anchor=\"middle\" x=\"334\" y=\"-406.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [35, 35]</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>1</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"324.75,-365 223.25,-365 223.25,-297 324.75,-297 324.75,-365\"/>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-347.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">x[1] &lt;= 2.7</text>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-332.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.229</text>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-317.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 38</text>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-302.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [33, 5]</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M314.35,-400.6C309.59,-392.5 304.43,-383.72 299.44,-375.24\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"302.54,-373.62 294.46,-366.78 296.51,-377.17 302.54,-373.62\"/>\n",
       "<text text-anchor=\"middle\" x=\"287.42\" y=\"-383.87\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">True</text>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"444.75,-365 343.25,-365 343.25,-297 444.75,-297 444.75,-365\"/>\n",
       "<text text-anchor=\"middle\" x=\"394\" y=\"-347.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">x[1] &lt;= 3.8</text>\n",
       "<text text-anchor=\"middle\" x=\"394\" y=\"-332.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.117</text>\n",
       "<text text-anchor=\"middle\" x=\"394\" y=\"-317.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 32</text>\n",
       "<text text-anchor=\"middle\" x=\"394\" y=\"-302.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [2, 30]</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;10 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>0&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M353.65,-400.6C358.41,-392.5 363.57,-383.72 368.56,-375.24\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"371.49,-377.17 373.54,-366.78 365.46,-373.62 371.49,-377.17\"/>\n",
       "<text text-anchor=\"middle\" x=\"380.58\" y=\"-383.87\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">False</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>2</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"205,-261 111,-261 111,-193 205,-193 205,-261\"/>\n",
       "<text text-anchor=\"middle\" x=\"158\" y=\"-243.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">x[0] &lt;= 4.7</text>\n",
       "<text text-anchor=\"middle\" x=\"158\" y=\"-228.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.32</text>\n",
       "<text text-anchor=\"middle\" x=\"158\" y=\"-213.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 5</text>\n",
       "<text text-anchor=\"middle\" x=\"158\" y=\"-198.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [1, 4]</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M236.02,-296.6C226,-287.8 215.08,-278.19 204.67,-269.03\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"207.03,-266.45 197.2,-262.47 202.4,-271.7 207.03,-266.45\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"324.75,-261 223.25,-261 223.25,-193 324.75,-193 324.75,-261\"/>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-243.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">x[1] &lt;= 3.05</text>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-228.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.059</text>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-213.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 33</text>\n",
       "<text text-anchor=\"middle\" x=\"274\" y=\"-198.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [32, 1]</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;5 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>1&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M274,-296.6C274,-289.03 274,-280.87 274,-272.9\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"277.5,-272.99 274,-262.99 270.5,-272.99 277.5,-272.99\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>3</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"94,-149.5 0,-149.5 0,-96.5 94,-96.5 94,-149.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"47\" y=\"-132.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"middle\" x=\"47\" y=\"-117.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 1</text>\n",
       "<text text-anchor=\"middle\" x=\"47\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [1, 0]</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M121.65,-192.6C109.33,-181.27 95.56,-168.62 83.24,-157.3\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"85.82,-154.92 76.09,-150.73 81.08,-160.07 85.82,-154.92\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"206,-149.5 112,-149.5 112,-96.5 206,-96.5 206,-149.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"159\" y=\"-132.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"middle\" x=\"159\" y=\"-117.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 4</text>\n",
       "<text text-anchor=\"middle\" x=\"159\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 4]</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M158.33,-192.6C158.43,-182.47 158.54,-171.28 158.64,-160.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"162.13,-161.25 158.73,-151.22 155.14,-161.18 162.13,-161.25\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"320,-157 226,-157 226,-89 320,-89 320,-157\"/>\n",
       "<text text-anchor=\"middle\" x=\"273\" y=\"-139.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">x[0] &lt;= 5.2</text>\n",
       "<text text-anchor=\"middle\" x=\"273\" y=\"-124.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.32</text>\n",
       "<text text-anchor=\"middle\" x=\"273\" y=\"-109.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 5</text>\n",
       "<text text-anchor=\"middle\" x=\"273\" y=\"-94.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [4, 1]</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M273.67,-192.6C273.6,-185.03 273.52,-176.87 273.44,-168.9\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"276.94,-168.95 273.34,-158.99 269.94,-169.02 276.94,-168.95\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"439.75,-149.5 338.25,-149.5 338.25,-96.5 439.75,-96.5 439.75,-149.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"389\" y=\"-132.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"middle\" x=\"389\" y=\"-117.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 28</text>\n",
       "<text text-anchor=\"middle\" x=\"389\" y=\"-102.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [28, 0]</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;9 -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>5&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M311.66,-192.6C324.43,-181.27 338.69,-168.62 351.46,-157.3\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"353.73,-159.96 358.89,-150.71 349.08,-154.73 353.73,-159.96\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"264,-53 170,-53 170,0 264,0 264,-53\"/>\n",
       "<text text-anchor=\"middle\" x=\"217\" y=\"-35.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"middle\" x=\"217\" y=\"-20.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 4</text>\n",
       "<text text-anchor=\"middle\" x=\"217\" y=\"-5.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [4, 0]</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M253.26,-88.68C248.38,-80.45 243.13,-71.59 238.18,-63.25\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"241.23,-61.51 233.12,-54.7 235.2,-65.08 241.23,-61.51\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"376,-53 282,-53 282,0 376,0 376,-53\"/>\n",
       "<text text-anchor=\"middle\" x=\"329\" y=\"-35.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"middle\" x=\"329\" y=\"-20.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 1</text>\n",
       "<text text-anchor=\"middle\" x=\"329\" y=\"-5.7\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 1]</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;8 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>6&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M292.74,-88.68C297.62,-80.45 302.87,-71.59 307.82,-63.25\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"310.8,-65.08 312.88,-54.7 304.77,-61.51 310.8,-65.08\"/>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\">\n",
       "<title>11</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"444.75,-253.5 343.25,-253.5 343.25,-200.5 444.75,-200.5 444.75,-253.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"394\" y=\"-236.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"middle\" x=\"394\" y=\"-221.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 30</text>\n",
       "<text text-anchor=\"middle\" x=\"394\" y=\"-206.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 30]</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M394,-296.6C394,-286.47 394,-275.28 394,-264.93\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"397.5,-265.22 394,-255.22 390.5,-265.22 397.5,-265.22\"/>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\">\n",
       "<title>12</title>\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"557,-253.5 463,-253.5 463,-200.5 557,-200.5 557,-253.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"510\" y=\"-236.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\n",
       "<text text-anchor=\"middle\" x=\"510\" y=\"-221.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 2</text>\n",
       "<text text-anchor=\"middle\" x=\"510\" y=\"-206.2\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [2, 0]</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;12 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>10&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M431.98,-296.6C444.87,-285.27 459.25,-272.62 472.13,-261.3\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"474.43,-263.94 479.63,-254.71 469.81,-258.68 474.43,-263.94\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.sources.Source at 0x31834b190>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "# data\n",
    "def create_data():\n",
    "    iris = load_iris()\n",
    "    df = pd.DataFrame(iris.data, columns=iris.feature_names)\n",
    "    df['label'] = iris.target\n",
    "    df.columns = [\n",
    "        'sepal length', 'sepal width', 'petal length', 'petal width', 'label'\n",
    "    ]\n",
    "    data = np.array(df.iloc[:100, [0, 1, -1]])\n",
    "    # print(data)\n",
    "    return data[:, :2], data[:, -1]\n",
    "\n",
    "\n",
    "X, y = create_data()\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)\n",
    "\n",
    "clf = DecisionTreeClassifier()\n",
    "clf.fit(X_train, y_train,)\n",
    "print(f'The accuracy score used DecisionTreeClassifier to predict is {clf.score(X_test, y_test) * 100:.2f}%')\n",
    "\n",
    "\n",
    "# 导出决策树的可视化文件，文件格式是dot\n",
    "dot_data = tree.export_graphviz(clf, out_file=None)\n",
    "# 使用graphviz包，对决策树进行展示\n",
    "graph = graphviz.Source(dot_data)\n",
    "# 可使用view方法展示决策树\n",
    "# 中文乱码：需要对源码_export.py文件（文件路径：sklearn/tree/_export.py）修改，\n",
    "# 在文件第451行中将helvetica改成SimSun\n",
    "graph"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
